#ifndef VL_LLIST_HPP
#define VL_LLIST_HPP

#include <iterator>
#include <cstddef>
#include <algorithm>

namespace vl
{

struct default_list_tag
{};

struct list_node_common
{
	list_node_common()
	{
		next_ = this;
		prev_ = this;
	}
	
	list_node_common* next_;
	list_node_common* prev_;
	
	void unlink()
	{
		prev_->next_ = next_;
		next_->prev_ = prev_;
	}
	
	template<typename ListT>
	void move_to(ListT& dest)
	{
		unlink();
		dest.list_common::push_back(this);
	}
};

template<typename T, typename Op>
bool do_list_compare(void* comparer, list_node_common* a, list_node_common* b)
{
	Op& real_comparer = *static_cast<Op*>(comparer);
	return real_comparer(*static_cast<T*>(a), *static_cast<T*>(b));
}

typedef bool (*do_list_compare_func)(void*, list_node_common*, list_node_common*);

template<class T, typename Tag = default_list_tag>
struct list_node : list_node_common
{
	T* next()
	{
		return static_cast<T*>(next_);
	}

	T* prev()
	{
		return static_cast<T*>(prev_);
	}
};

template<typename T, typename Tag>
inline T* node_downcast(list_node_common* p)
{
	return static_cast<T*>(static_cast<list_node<T, Tag>*>(p));
}

template<typename T, typename Tag>
inline list_node<T, Tag>* node_upcast(T* p)
{
	return static_cast<list_node<T, Tag>*>(p);
}

struct list_common
{
	list_common()
	{
		sentinel_.next_ = &sentinel_;
		sentinel_.prev_ = &sentinel_;
	}

	list_node_common* push_back(list_node_common* el);

	std::size_t size();

	list_node_common* unlink(list_node_common* i);
	
	void unlink_all()
	{
		sentinel_.next_ = &sentinel_;
		sentinel_.prev_ = &sentinel_;
	}
	
	
	list_node_common* raw_first() const { return sentinel_.next_; }
	list_node_common* raw_last() const { return sentinel_.prev_; }
	list_node_common* sentinel() { return &sentinel_; }

	list_node_common* insert(list_node_common* b, list_node_common* el);
	list_node_common* insert_after(list_node_common* b, list_node_common* el);

	void swap(list_common& b);

	void sort(void* comparer, do_list_compare_func do_compare);
	
	list_node_common* first() { return sentinel_.next_; }
	list_node_common* last() { return sentinel_.prev_; }

	list_node_common sentinel_;
};

struct default_delete
{
	template<typename T>
	void operator()(T* p)
	{
		delete p;
	}
};

struct dummy_delete
{
	template<typename T>
	void operator()(T* p)
	{
		// Do nothing
	}
};

struct default_ownership
{
	template<typename T>
	T* take(T* p)
	{
		return p; // Verbatim
	}
	
	/*
	template<typename T>
	T* release(T* p)
	{
		return p;
	}*/
	
	/* Transfering assumes no ownership action
	template<typename T, typename ListT>
	T* transfer(T* p, ListT& from, ListT& to) // When transfering ownership from one list to another (both the same type)
	{
		return p;
	}*/
};

template<
	typename T,
	typename Deleter = default_delete,
	typename Tag = default_list_tag,
	typename Ownership = default_ownership>
struct list : list_common, protected Deleter, protected Ownership
{
	struct iterator
	{
		typedef ptrdiff_t difference_type;
		typedef std::bidirectional_iterator_tag iterator_category;
		typedef T* pointer;
		typedef T& reference;
		typedef T value_type;
    
		iterator()
		: ptr_(0)
		{
		}

		iterator(list_node_common* ptr)
		: ptr_(ptr)
		{
		}
		
		iterator(T* ptr)
		: ptr_(node_upcast<T, Tag>(ptr))
		{
		}

		T& operator*()
		{
			return *node_downcast<T, Tag>(ptr_);
		}

		T* operator->()
		{
			return node_downcast<T, Tag>(ptr_);
		}

		iterator& operator++()
		{
			ptr_ = ptr_->next_;
			return *this;
		}

		iterator& operator--()
		{
			ptr_ = ptr_->prev_;
			return *this;
		}
		
		iterator next() const
		{
			return iterator(ptr_->next_);
		}
		
		iterator prev() const
		{
			return iterator(ptr_->prev_);
		}

		bool operator==(iterator const& b)
		{
			return b.ptr_ == ptr_;
		}

		bool operator!=(iterator const& b)
		{
			return b.ptr_ != ptr_;
		}
		
		operator T*()
		{
			return node_downcast<T, Tag>(ptr_);
		}

		list_node_common* ptr_;
	};
	
	struct reverse_iterator
	{
		typedef ptrdiff_t difference_type;
		typedef std::bidirectional_iterator_tag iterator_category;
		typedef T* pointer;
		typedef T& reference;
		typedef T value_type;
    
		reverse_iterator()
		: ptr_(0)
		{
		}

		reverse_iterator(list_node_common* ptr)
		: ptr_(ptr)
		{
		}
		
		reverse_iterator(T* ptr)
		: ptr_(node_upcast<T, Tag>(ptr))
		{
		}

		T& operator*()
		{
			return *node_downcast<T, Tag>(ptr_);
		}

		T* operator->()
		{
			return node_downcast<T, Tag>(ptr_);
		}

		reverse_iterator& operator++()
		{
			ptr_ = ptr_->prev_;
			return *this;
		}

		reverse_iterator& operator--()
		{
			ptr_ = ptr_->next_;
			return *this;
		}
		
		reverse_iterator next() const
		{
			return reverse_iterator(ptr_->prev_);
		}
		
		reverse_iterator prev() const
		{
			return reverse_iterator(ptr_->next_);
		}

		bool operator==(reverse_iterator const& b)
		{
			return b.ptr_ == ptr_;
		}

		bool operator!=(reverse_iterator const& b)
		{
			return b.ptr_ != ptr_;
		}
		
		operator T*()
		{
			return node_downcast<T, Tag>(ptr_);
		}

		list_node_common* ptr_;
	};
	
	list(Deleter const& deleter = Deleter(), Ownership const& ownership = Ownership())
	: Deleter(deleter)
	, Ownership(ownership)
	{
	}
	
	list(list const& b)
	{
		// TODO: Add proper cloning semantics
		for(list_node_common* f = b.first(); f != &b.sentinel_; f = f->next_)
		{
			push_back(Ownership::take(new T(*node_downcast<T, Tag>(f))));
		}
	}
	
	~list()
	{
		clear();
	}

	T* first() const { return node_downcast<T, Tag>(sentinel_.next_); }
	T* last() const { return node_downcast<T, Tag>(sentinel_.prev_); }
	
	iterator push_back(T* el)
	{
		el = static_cast<T*>(Ownership::take(el));
		return iterator(list_common::push_back(node_upcast<T, Tag>(el)));
	}
	
	iterator relink_back(T* el)
	{
		return iterator(list_common::push_back(node_upcast<T, Tag>(el)));
	}

	void pop_back()
	{
		erase(iterator(raw_last()));
	}

	void pop_front()
	{
		erase(iterator(raw_first()));
	}
	
	void unlink_back()
	{
		list_common::unlink(raw_last());
	}
	
	void unlink_front()
	{
		list_common::unlink(raw_first());
	}

	iterator erase(iterator i)
	{
		iterator n(list_common::unlink(i.ptr_));
		Deleter::operator()(node_downcast<T, Tag>(i.ptr_));

		return n;
	}

	iterator begin()
	{
		return iterator(raw_first());
	}

	iterator end()
	{
		return iterator(&sentinel_);
	}
	
	reverse_iterator rbegin()
	{
		return reverse_iterator(raw_last());
	}

	reverse_iterator rend()
	{
		return reverse_iterator(&sentinel_);
	}

	T& front()
	{
		return *first();
	}

	T& back()
	{
		return *last();
	}

	bool empty()
	{
		return sentinel_.next_ == &sentinel_;
	}
	
	bool is_end(T* p)
	{
		return node_upcast<T, Tag>(p) == &sentinel_;
	}
	
	/*
	size_t size()
	{
		return list_common::size();
	}*/

	iterator unlink(T* i)
	{
		return iterator(list_common::unlink(node_upcast<T, Tag>(i)));
	}
	
	iterator relink(iterator b, T* el)
	{
		return iterator(
			list_common::insert(
				b.ptr_,
				node_upcast<T, Tag>(el)));
	}
	
	reverse_iterator relink(reverse_iterator b, T* el)
	{
		return reverse_iterator(
			list_common::insert_after(
				b.ptr_,
				node_upcast<T, Tag>(el)));
	}
	
	iterator insert(iterator b, T* el)
	{
		return iterator(
			list_common::insert(
				b.ptr_,
				node_upcast<T, Tag>(
					Ownership::take(el))));
	}
	
	reverse_iterator insert(reverse_iterator b, T* el)
	{
		return reverse_iterator(
			list_common::insert_after(
				b.ptr_,
				node_upcast<T, Tag>(
					Ownership::take(el))));
	}
	
	template<typename Compare>
	iterator insert_sorted(T* el, Compare compare)
	{
		el = Ownership::take(el);
		
		list_node_common* before = &sentinel_;
		list_node_common* after = before->next_;
		while(after != &sentinel_ && compare(*node_downcast<T, Tag>(after), *el))
		{
			before = after;
			after = after->next_;
		}
		
		return iterator(list_common::insert(after, node_upcast<T, Tag>(el)));
	}
	
	void move_to(iterator i, list& dest)
	{
		list_common::unlink(i.ptr_);
		dest.list_common::push_back(i.ptr_);
	}

	/* Handled fine by list_common::unlink_all when there are no Ownership release
	void unlink_all()
	{
		for(list_node_common* n = sentinel_.next_; n != &sentinel_; n = n->next_)
		{
			Ownership::release(n);
		}
		
		list_common::unlink_all();
	}*/

	void clear()
	{
		for(list_node_common* n = sentinel_.next_; n != &sentinel_;)
		{
			list_node_common* next = n->next_;
			Deleter::operator()(node_downcast<T, Tag>(n));
			n = next;
		}

		list_common::unlink_all();
	}
		
	void splice(list& b)
	{
		if(!b.empty())
		{
			b.sentinel_.next_->prev_ = sentinel_.prev_;
			b.sentinel_.prev_->next_ = &sentinel_;
			
			sentinel_.prev_->next_ = b.sentinel_.next_;
			sentinel_.prev_ = b.sentinel_.prev_;
			
			b.list_common::unlink_all();
		}
	}

	template<class Op>
	void sort(Op op)
	{
		list_common::sort(&op, do_list_compare<T, Op>);
	}
	
	template<typename Op>
	void merge(list& b, Op op)
	{
		iterator i = b.begin();
		
		if(i == b.end())
			return; // Nothing to splice
			
		iterator after = begin();
		
		for(; after != end(); ++after)
		{
			T const& a = *after;
			while(op(*i, a))
			{
				iterator next = i.next();
				b.unlink(i);
				relink(after, i);
				i = next;
				if(i == b.end())
					return;
			}
		}
		
		if(!b.empty())
		{
			splice(b); // Splice in the rest of the list
		}
	}
	
	template<typename Op>
	list_node_common* _merge(list_node_common* first, list_node_common* second, Op& op)
	{
		if(!first)
			return second;
		else if(!second)
			return first;
			
		list_node_common* a = first;
		list_node_common* b = second;
		list_node_common* prev;
		
		if(op(*node_downcast<T, Tag>(b), *node_downcast<T, Tag>(a)))
		{
			first = b;
			prev = b;
			b = b->next_;
		}
		else
		{
			prev = a;
			a = a->next_;
		}
			
		while(a && b)
		{
			if(op(*node_downcast<T, Tag>(b), *node_downcast<T, Tag>(a)))
			{
				prev->next_ = b;
				prev = b;
				b = b->next_;
			}
			else
			{
				prev->next_ = a;
				prev = a;
				a = a->next_;
			}
		}
		
		// Check if there's left-overs in any of the lists
		if(a)
			prev->next_ = a;
		else if(b)
			prev->next_ = b;
		
		return first;
	}
	
	template<typename Op>
	void sort_fast(Op op)
	{
		if(empty())
			return;
			
		std::size_t const MaxBins = 25;
		list_node_common* binlist[MaxBins] = {};
		
		raw_last()->next_ = 0; // Decycle chain
		list_node_common* el = raw_first();
				
		std::size_t max_bin = 0;
		
		while(el)
		{
			// Splice into temp and move el to the next element
			list_node_common* temp = el;
			el = el->next_;
			temp->next_ = 0;
			
			std::size_t bin = 0;
			for(; bin < max_bin && binlist[bin]; ++bin)
			{
				temp = _merge(binlist[bin], temp, op);
				binlist[bin] = 0;
			}
			
			if(bin == MaxBins)
			{
				binlist[bin - 1] = _merge(binlist[bin - 1], temp, op);
			}
			else
			{
				binlist[bin] = temp;
				if(bin == max_bin)
					++max_bin;
			}
		}
		
		for(std::size_t bin = 1; bin < max_bin; ++bin)
		{
			binlist[bin] = _merge(binlist[bin], binlist[bin - 1], op);
		}
		
		sentinel_.next_ = binlist[max_bin - 1];
		
		// Fix back pointers and stitch up
		list_node_common* prev = &sentinel_;
		list_node_common* cur = sentinel_.next_;
		for(; cur; cur = cur->next_)
		{
			cur->prev_ = prev;
			prev = cur;
		}
		
		prev->next_ = &sentinel_;
		sentinel_.prev_ = prev;
	}
	
	/* Cross events are a too specific functionality
	struct dummy_cross_event
	{
		void operator()(T const&, T const&) const
		{
			// Do nothing
		}
	};*/
	
	template<typename Op/*, typename CrossEvent*/>
	void insertion_sort(Op op/*, CrossEvent cross_event = dummy_cross_event()*/)
	{
		list_node_common* sent = &sentinel_;
		list_node_common* prev = sent;
		list_node_common* cur = prev->next_;
		
		while(cur != sent)
		{
			list_node_common* next = cur->next_;
			T const* curt = node_downcast<T, Tag>(cur);
			if(prev != sent
			&& op(*curt, *node_downcast<T, Tag>(prev)))
			{
				//cross_event(*node_downcast<T, Tag>(prev), *node_downcast<T, Tag>(cur));
				
				// Unlink
				prev->next_ = next;
				next->prev_ = prev;
				
				list_node_common* before = prev->prev_;
				list_node_common* after = prev;
				
				while(before != sent
				&& op(*curt, *node_downcast<T, Tag>(before)))
				{
					//cross_event(*node_downcast<T, Tag>(before), *node_downcast<T, Tag>(cur));
					after = before;
					before = after->prev_;
				}

				cur->next_ = after;
				cur->prev_ = before;
				
				before->next_ = cur;
				after->prev_ = cur;
				
				// prev stays the same here
			}
			else
				prev = cur; // No move, prev will be cur
			
			cur = next;
		}
	}
};

}

#endif //VL_LLIST_HPP
